package com.LeeCode;

/**
 * 二叉树中的最长交错路径
 */

public class Code1372 {
    public static void main(String[] args) {
        Integer[] arr = {1, 1, 1, null, 1, null, null, 1, 1, null, 1};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1372().longestZigZag(root));
    }

    private int ans = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root);
        return ans;
    }

    // 自底向上
    private int[] dfs(TreeNode root) {
        if (root == null) return new int[]{-1, -1};
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);

        int leftLen = left[1] + 1;
        int rightLen = right[0] + 1;

        ans = Math.max(ans, Math.max(leftLen, rightLen));

        return new int[]{leftLen, rightLen};
    }

}
